\documentclass[13pt]{beamer}
%\usetheme{berlin}
\usetheme{Berkeley}
%\usetheme{Warsaw}

%\usepackage[polish]{babel}
%\usepackage[cp1250]{inputenc}
%\usepackage[latin2]{inputenc}

\usepackage{tikz}

\usepackage{polski}
\usepackage[T1]{fontenc}
%\usepackage[cp1250]{inputenc}

%\usepackage[T4]{fontenc} 
\usepackage[polish]{babel}
%\usepackage[cp1250]{inputenc}

\usepackage[utf8x]{inputenc}

%\usepackage[utf8x]{inputenc}
%\usepackage{polski}
%\usepackage[T1]{fontenc}

%\usepackage{default}
\title[Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych\hspace{2em}\insertframenumber/
\inserttotalframenumber]{Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych}
%\title{Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych}
\author{Łukasz Szybka}
\date{\today}
\begin{document}

%\onehalfspacing
\linespread{1.2}
%\baselineskip{16}
%\renewcommand\baselinestretch{1.5}



\frame{\titlepage}

\section[Spis]{}
\frame{\tableofcontents}

\section[Wstęp]{Wstęp}

\frame
{
  \frametitle{Problemy NP-zupełne}
  \begin{itemize}
  \item Cechą problemów NP-zupełnych jest to, że nie jest znany algorytm szybkiego znajdowania rozwiązań
  \item Czas potrzebny na znalezienie rozwiązania problemu NP-zupełnego wzrasta bardzo szybko w miarę zwiększenia rozmiaru problemu
  \end{itemize}
}


\frame
{
  \frametitle{Przykłady problemów NP-zupełnych}
  \begin{itemize}
  \item Kolorowanie grafu
  \item Problem komiwojażera
  \item Problem plecakowy
  \item Tetris
  \item Saper
  \item Sudoku
  \end{itemize}
}


\frame
{
  \frametitle{„Inteligentne” metody rozwiązywania problemów stosowane w informatyce}
  \begin{itemize}
  \item Sieci neuronowe
  \item Algorytmy genetyczne
  \item Logika rozmyta
  \end{itemize}
}

\section[Algorytmy genetyczne]{Algorytmy genetyczne}

\frame
{
  \frametitle{Algorytm genetyczny}
  \begin{itemize}
    \item Przeszukanie puli możliwych rozwiązań w celu znalezienia najlepszych
    \item Sposób poszukiwania rozwiązania naśladujący naturalny proces ewolucji
    \item Możliwe znalezienie rozwiązania w krótkim czasie nawet dla bardzo złożonych problemów
    \item Szybsze niż tradycyjne algorytmy w przypadku problemów NP-zupełnych
    \item Możliwe rozwiązania sub-optymalne
  \end{itemize}
}

\frame
{
  \frametitle{Założenia}
  \begin{itemize}
    \item Rozwiązania problemu kodujemy za pomocą chromosomów o określonej długości
    \item Definiujemy środowisko i jego parametry (prawdopodobieństwo mutacji, sposób oceny i wyboru najlepszych osobników)
    \item Definiujemy populację określonej wielkości
  \end{itemize}
}

\frame
{
  \frametitle{Funkcja oceny}
  \begin{itemize}
  \item Zadaniem funkcji oceny jest określenie które osobniki w populacji najlepiej spełniają warunki zadania
  \item Przyporządkowuje każdemu osobnikowi liczbową wartość która odpowiada jego przystosowaniu
  \item Oblicza dostosowanie całej populacji
  \end{itemize}
}

\frame
{
  \frametitle{Metody selekcji}
  Na podstwie obliczonych wartości dostosowania osobników wybieramy te najlepsze
  \begin{itemize}
  \item Metoda ruletki
  \item Metoda rankingowa
  \item Metoda turniejowa
  \end{itemize}
}

\frame
{
  \frametitle{Krzyżowanie}
  Losowo wybieramy punkt krzyżowania\\
  Możliwe różne warianty krzyżowania (np. wielopunktowe)\\
  \begin{center}
      \begin{tabular}{ | l | l |}
      \hline
      Osobnik1 & \texttt {{\color{red}101}|{\color{red}101001}}\\ \hline
      Osobnik2 & \texttt {{\color{blue}011}|{\color{blue}001101}}\\ \hline
      potomek1 & \texttt {{\color{red}101}|{\color{blue}001101}}\\ \hline
      potomek2 & \texttt {{\color{blue}011}|{\color{red}101001}}\\ \hline

      \end{tabular}
  \end{center}
}

\frame
{
  \frametitle{Mutacja}
  Dzięki mutacji unikamy przedwczesnej zbieżności do rozwiązań sub-optymalnych\\
  Różne rodzaje mutacji\\
  \begin{center}
      \begin{tabular}{ | l | l |}
      \hline
      przed mutacją & \texttt {101101001}\\ \hline
      osobnik zmutowany & \texttt {101101{\color{red}1}01}\\ \hline

      \end{tabular}
  \end{center}
}

\frame
{
  \frametitle{Warunek zakończenia}
  \begin{itemize}
  \item Osiągnięcie zadanej liczby generacji
  \item Brak poprawy w kilku ostatnich pokoleniach
  \item Znalezienie rozwiązania optymalnego (w przypadku problemów gdzie można to stwierdzić)
  \end{itemize}

}

\frame
{
  \frametitle{Schemat blokowy algorytmu genetycznego}
	\begin{figure}
          \scalebox{0.4}
	  {
	    \input{../Schemat_blokowy_algorytmu_genetycznego}
	  }
	  %\centering
	  %\includegraphics[width=8cm]{Schemat_blokowy_algorytmu_genetycznego.jpeg}
	  %\input{Schemat_blokowy_algorytmu_genetycznego}
	  %\caption{Schemat blokowy algorytmu}
	  %\label{fig:block_diagram_algorithm}
	\end{figure}

  %\begin{overprint}
    
  %\end{overprint} 
}


\section[Moja praca]{Moja praca}

\frame
{
  \frametitle{Moja praca}
  \begin{itemize}
  \item Napisanie biblioteki wspomagającej obliczenia za pomocą algorytmów genetycznych
  \item Zastosowanie do rozwiązania kilku zagadnień
  \item Analiza najlepszych parametrów środowiska
  \item Analiza wyników, porównanie z innymi metodami poszukiwania rozwiązań
  \end{itemize}

}

\frame
{
  \frametitle{Planowane zagadnienia}
  \begin{itemize}
  \item Poszukiwanie maksimum funkcji w zadanym przedziale
  \item Problem komiwojażera
  \item Sudoku
  \end{itemize}
}

\frame
{
  \frametitle{Problemy}
  \begin{itemize}
  \item Dobranie odpowiedniego kodowania informacji w chromosomie
  \item Dobranie parametrów środowiska
  \item Dobranie dodatkowych operatorów oprócz krzyżowania i mutacji w celu poprawy wyników
  \item Zaprojektowanie biblioteki umożliwiającej łatwe modyfikacje i dopasowanie do różnych problemów
  \end{itemize}
}

\frame
{
  \frametitle{Wybrane technologie}
  \begin{itemize}
  \item C++
  \item Biblioteka Qt 4.6
  \item Dokumentacja kodu Doxygen
  \end{itemize}
}

\frame
{
  \frametitle{Co już jest}
	\begin{figure}
	  %\centering
	  \includegraphics[width=9cm]{../class_diagram.png}
	  %\caption{Diagram klas}
	  \label{fig:class_diagram}
	\end{figure}
}

\frame
{
  \frametitle{Źródła}
  \begin{itemize}
    \item \href{http://www.devblogi.pl/2010/02/twoje-ulubione-oszustwo-zwiazane-z-np.html}{http://www.devblogi.pl/}
    \item \href{http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/800px-P_np_np-complete_np-hard.svg.png}{Wikipedia}
    \item \href{http://www.staff.amu.edu.pl/~lipowski/java/genetic/genetic.html}{http://www.staff.amu.edu.pl/}
    \item \href{http://tim.hibal.org/blog/?p=40}{http://tim.hibal.org/blog}
    \item \href{http://pl.wikipedia.org/wiki/Logika_rozmyta}{Wikipedia - Logika rozmyta}
    \item \href{http://www.nitrogen.za.org/viewtutorial.asp?id=4}{http://www.nitrogen.za.org/}
    \item \href{http://en.wikipedia.org/wiki/List_of_NP-complete_problems}{List of NP-complete problems}
    \item \href{http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm}{http://web.mat.bham.ac.uk/}
    \item \href{http://www.claymath.org/Popular_Lectures/Minesweeper/}{Minesweeper}
  \end{itemize}
}

\end{document}
